﻿//void BackMerge(int* a, int begin, int end) {
//	if (begin >= end) {
//		return;
//	}
//	BackMerge(a, begin, (begin + end) / 2);
//	BackMerge(a, (begin + end) / 2 + 1, end);
//	int leftbegin = begin, leftend = (begin + end) / 2;
//	int rightbegin = leftend + 1, rightend = end;
//	int* nums = (int*)malloc(sizeof(int) * (end + 1));
//	memset(nums, 0, sizeof(int) * (end + 1));
//	int i = 0;
//	while (leftbegin <= leftend && rightbegin <= rightend) {
//		if (a[leftbegin] < a[rightbegin]) {
//			nums[i++] = a[leftbegin++];
//		}
//		else {
//			nums[i++] = a[rightbegin++];
//		}
//	}
//	while (leftbegin >= leftend && rightbegin <= rightend) {
//		nums[i++] = a[rightbegin++];
//	}
//	while (rightbegin >= rightend && leftbegin <= leftend) {
//		nums[i++] = a[leftbegin++];
//	}
//	memcpy(a + begin, nums, sizeof(int) * (end - begin + 1));
//	free(nums);
//}
//
//void CountSort(int* a, int n) {
//	int min = a[0], max = a[0];
//	for (int i = 0; i < n; i++) {
//		if (min > a[i]) {
//			min = a[i];
//		}
//		if (max < a[i]) {
//			max = a[i];
//		}
//	}
//	int* Count = (int*)malloc(sizeof(int) * (max + 1));
//	assert(Count);
//	memset(Count, 0, sizeof(int) * (max + 1));
//	for (int i = 0; i < n; i++) {
//		Count[a[i]]++;
//	}
//	int j = 0;
//	for (int i = 0; i < max + 1; i++) {
//		while (Count[i]--) {
//			a[j++] = i;
//		}
//	}
//	free(Count);
//}

//void BackMerge2(int* a, int n) {
//	int grep = 1;
//	while (grep < n) {
//		for (int i = 0; i < n; i += 2 * grep) {
//			int leftbegin = i, leftend = leftbegin + grep - 1;
//			int rightbegin = leftend + 1, rightend = rightbegin + grep - 1;
//			if (rightbegin >= n) {
//				break;
//			}
//			if (rightend >= n) {
//				rightend = n - 1;
//			}
//			int* nums = (int*)malloc(sizeof(int) * (rightend - leftbegin + 1));
//			assert(nums);
//			memset(nums, 0, sizeof(int) * (rightend - leftbegin + 1));
//			int j = 0;
//			while (leftbegin <= leftend && rightbegin <= rightend) {
//				if (a[leftbegin] < a[rightbegin]) {
//					nums[j++] = a[leftbegin++];
//				}
//				else {
//					nums[j++] = a[rightbegin++];
//				}
//			}
//			while (leftbegin >= leftend && rightbegin <= rightend) {
//				nums[j++] = a[rightbegin++];
//			}
//			while (rightbegin >= rightend && leftbegin <= leftend) {
//				nums[j++] = a[leftbegin++];
//			}
//			memcpy(a + i, nums, sizeof(int) * (rightend - i + 1));
//			free(nums);
//		}
//		grep *= 2;
//	}
//}